//
// Created by Semir on 2020/6/1.
//

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int numDecodings(const string& s, vector<int>& record, int index) {
    if (index > s.length()) {
        return 0;
    }
    if (index == s.length()) {
        return 1;
    }
    if (record[index] >= 0) {
        return record[index];
    }
    int n = s[index] - '0';
    int res;
    if (n == 0) {
        res = numDecodings(s, record, index + 1);
    } else if (n < 3 && s[index + 1] - '0' > 0 && s[index + 1] - '0' < 7) {
        if (s[index + 1] - '0' == 0) {
            res = numDecodings(s, record, index + 2);
        } else if (s[index + 1] - '0' < 7) {
            res = numDecodings(s, record, index + 1) + numDecodings(s, record, index + 2);
        }
    } else {
        res = numDecodings(s, record, index + 1);
    }
    record[index] = res;
    return res;
}

int numDecodings(string s) {
    vector<int> record(s.length(), -1);
    if (s == "0") {
        return 0;
    }
    return numDecodings(s, record, 0);
}

int main() {
    string str = "30";
    int res = numDecodings(str);
    cout << res << endl;
    return 0;
}